import javax.swing.tree.TreeNode;
import java.util.HashMap;
import java.util.Map;

/**
 * @Author: code.rookie
 * @ClassName: PostorderTraversal
 * @Date: 2021/10/18 4:02 下午
 * @PACKAGE_NAME: PACKAGE_NAME
 * @Version: 1
 * @Description 106. 从中序与后序遍历序列构造二叉树
 */
public class PostorderTraversal {

    //   输入： 中序遍历 inorder = [9,3,15,20,7]
//         后序遍历 postorder = [9,15,7,20,3]
//   输出：     3
//            / \
//            9  20
//            /  \
//            15  7
    Map<Integer, Integer> map = new HashMap<>();
    int rootIndex = 0;

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        int i = 0;
        for (int val : inorder) {
            map.put(val, i++);
        }
        rootIndex = postorder.length - 1;
        return helper(inorder, postorder, 0, rootIndex);


    }

    public TreeNode helper(int[] inorder, int[] postorder, int leftIdx, int rightIdx) {
        if (leftIdx > rightIdx) {
            return null;
        }
        TreeNode root = new TreeNode(postorder[rootIndex]);
        int index = map.get(root.val);
        rootIndex--;
        root.right = helper(inorder, postorder, index + 1, rightIdx);
        root.left = helper(inorder, postorder, leftIdx, index - 1);
        return root;
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

}
